package com.zry.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class BinaryTree {
    public static class TreeNode {

        int value;

        TreeNode left;

        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public static TreeNode arrayToTree(Integer[] input) {
        TreeNode root = createTreeNode(input, 1);
        return root;
    }
    
    //基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置
    private static TreeNode createTreeNode(Integer[] input, int index) {
        if (index <= input.length) {
            Integer value = input[index - 1];
            if (value != null) {
                TreeNode t = new TreeNode(value);

                t.left = createTreeNode(input, index * 2);
                t.right = createTreeNode(input, index * 2 + 1);
                return t;
            }
        }
        return null;
    }

    //前序遍历
    private static void frontPrintTree(TreeNode treeNode) {
        if (treeNode != null) {
            System.out.println(treeNode.value);
            frontPrintTree(treeNode.left);
            frontPrintTree(treeNode.right);
        }
    }

    //中序遍历
    private static void middlePrintTree(TreeNode treeNode) {
        if (treeNode != null) {
            middlePrintTree(treeNode.left);
            System.out.println(treeNode.value);
            middlePrintTree(treeNode.right);
        }
    }

    //后序遍历
    private static void endPrintTree(TreeNode treeNode) {
        if (treeNode != null) {
            endPrintTree(treeNode.left);
            endPrintTree(treeNode.right);
            System.out.println(treeNode.value);
        }
    }

    public static void main(String[] args) {
        Integer[] array = {1, 2, 3, 4, 5, null, 6};
        TreeNode treeNode = arrayToTree(array);
        System.out.println("***********front start************");
        frontPrintTree(treeNode);
        System.out.println("***********front end************");

        System.out.println("***********middle start************");
        middlePrintTree(treeNode);
        System.out.println("***********middle end************");

        System.out.println("***********end start************");
        endPrintTree(treeNode);
        System.out.println("***********end end************");

        levelIterator(treeNode);
    }

    //对层进行求平均数
    public static void levelIterator(TreeNode root) {
        if (root == null) {
            return;
        }
        //结果数据
        List<Float> result = new ArrayList<>();
        //借助队列实现层次遍历
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//将根节点入队

        while (!queue.isEmpty()) {
            float sum = 0;
            //每一层的节点个数
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();//出队队头元素并访问
                //对每一层进行求和
                sum += current.value;
                System.out.print("层遍历" + current.value + "-->");
                if (current.left != null)//如果当前节点的左节点不为空入队
                {
                    queue.offer(current.left);
                }
                if (current.right != null)//如果当前节点的右节点不为空，把右节点入队
                {
                    queue.offer(current.right);
                }
            }
            //每一层进行求平均数
            result.add(sum / size);
        }


        System.out.println(Arrays.toString(result.toArray()));
    }
}
